# 91/100 多维动态规划-不同路径
# leetcode第62题: https://leetcode.cn/problems/unique-paths/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/1/16
import math

from leetcode.test import test_function as tf


def uniquePaths(m: int, n: int) -> int:
    if m == 1 or n == 1:
        return 1

    dp = [[0] * n for _ in range(m)]
    dp[0] = [1] * n  # 首行赋值为1
    for i in range(m):  # 首列赋值为1
        dp[i][0] = 1

    for row in range(1, m):
        for col in range(n):
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1]

    return dp[m - 1][n - 1]


def uniquePaths_opt(m: int, n: int) -> int:
    if m == 1 or n == 1:
        return 1

    dp = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]  # 一种更好的赋值首行首列的方式

    for row in range(1, m):
        for col in range(n):
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1]

    return dp[m - 1][n - 1]


def uniquePaths_ultra(m: int, n: int) -> int:
    """由于 dp(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。"""
    if m == 1 or n == 1:
        return 1

    dp = [1] * n

    for row in range(1, m):
        for col in range(1, n):
            dp[col] += dp[col - 1]

    return dp[n - 1]


def uniquePaths_math(m: int, n: int) -> int:
    """从左上角到右下角的过程中，我们需要移动 m+n−2 次,其中有 m−1 次向下移动，n−1 次向右移动。
    因此路径的总数，就等于从 m+n−2 次移动中选择 m−1 次向下移动的方案数，即组合数C(n+m-2)(m-1)"""
    return math.comb(m + n - 2, n - 1)


if __name__ == '__main__':
    inp = [{"m": 3, "n": 7},
           {"m": 3, "n": 2},
           {"m": 3, "n": 3},
           {"m": 6, "n": 99},
           {"m": 96, "n": 99},
           ]
    out = [28, 3, 6, 87541245,
           703580609094219620976810136639537572562221837643188244800]
    tf(uniquePaths, inp, out)
    tf(uniquePaths_opt, inp, out)
    tf(uniquePaths_ultra, inp, out)
    tf(uniquePaths_math, inp, out)
